package cn.jathlon.datastructure;

import java.io.Serializable;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/***
 * A priority queue based on a binary heap. can find top k in a large data set(#N).
 * in O(NlogK) time in O(K) space
 * @author zhouqiang.pt
 *
 * @param <E>
 */
public class FixedBinaryHeapPriorityQueue<E> extends AbstractSet<E> implements
PriorityQueue<E>, Iterator<E>, Serializable, Cloneable{

	/**
	 */
	private static final long serialVersionUID = 1L;
	private int size;
	private int capacity;
	private List<E> elements;
	private double[] priorities;
	
	// constructors ----------------------------------------------------------
	public FixedBinaryHeapPriorityQueue(int capacity) {
		this.capacity = capacity;
		this.size = 0;
		this.elements = new ArrayList<E>();
		this.priorities = new double[capacity+1];
	}
	
	// iterator methods ------------------------------------------------------

		/**
		 * Returns true if the priority queue is non-empty
		 */
		public boolean hasNext() {
			return !isEmpty();
		}

		/**
		 * Returns the element in the queue with highest priority, and pops it from
		 * the queue.
		 */
		public E next() {
			return removeFirst();
		}

		/**
		 * Not supported -- next() already removes the head of the queue.
		 */
		public void remove() {
			throw new UnsupportedOperationException();
		}
	
	// PriorityQueue methods -------------------------------------------------

	public boolean replaceFirst(E key,double priority){
		elements.set(0, key);
		priorities[1] = priority;
		heapifyDown(1);
		return true;
	}
		
	@Override
	public E removeFirst() {
		E first = getFirst();
		swap(1, size);
		elements.remove(size-1);
		
		size--;
		heapifyDown(1);
		return first;
	}

	@Override
	public E getFirst() {
		if (this.size() > 0)
			return elements.get(0);
		throw new NoSuchElementException();
	}

	@Override
	public double getPriority() {
		if (this.size() > 0)
			return priorities[1];
		throw new NoSuchElementException();
	}

	
	/**
	 * Note that this method will be linear (not constant) time in this
	 * implementation! Better not to use it.
	 */
	@Override
	public double getPriority(E key) {
		for (int i = 0; i < elements.size(); i++) {
			if (elements.get(i).equals(key)) {
				return priorities[i];
			}
		}
		throw new NoSuchElementException();
	}

	@Override
	public boolean add(E key, double priority) {
		
		if (this.size < this.capacity) {
			elements.add(key);	
			priorities[size+1] = priority;	
			
			size++;
			heapifyUp(size);	
			return true;
		}
		else if(priority > this.getPriority()){
			return this.replaceFirst(key, priority);
		}
		else {
			return false;
		}

	}

	@Override
	public boolean changePriority(E key, double priority) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean relaxPriority(E key, double priority) {
		throw new UnsupportedOperationException();
	}

	@Override
	public List<E> toSortedList() {
		List<E> list = new ArrayList<E>();
		while (this.hasNext()) {
			list.add(this.next());
		}
		return list;
	}
	public List<E> findTopN() {
		List<E> list = new ArrayList<E>();
		while (this.hasNext()) {
			list.add(this.next());
		}
		int end = list.size() - 1 ;
		for (int begin = 0; begin < list.size()/2; begin++,end--) {
			E tmp = list.get(begin);
			list.set(begin,list.get(end));
			list.set(end, tmp);
		}
		return list;
	}
	
	@Override
	public String toString() {
		return this.toString(size());
	}

	@Override
	public Iterator<E> iterator() {
		return Collections.unmodifiableCollection(toSortedList()).iterator();
	}

	@Override
	public int size() {
		return this.size;
	}
	
	private void swap(int a,int b) {
		double tmpPriorites = priorities[a];
		priorities[a] = priorities[b];
		priorities[b] = tmpPriorites;
		
		E tmpEntity = elements.get(a-1);
		elements.set(a-1, elements.get(b-1));
		elements.set(b-1, tmpEntity);
		
		
	}
	
	private void heapifyDown(int pos)
	{
	     while( pos<<1<= size )
	     {
	         int t = pos<<1; 
	         if( (t + 1<= size) && (priorities[t+1]<priorities[t] )) t= t + 1;
	         if( priorities[t] < priorities[pos] )
	         {
	        	  swap(t,pos);
	              pos= t; 
	          }
	         else break;
	     }
	}
	
	private void heapifyUp(int pos) {
		while( pos>>1 >= 1 )
	    {
			int t = pos>>1;
	        if( priorities[t] > priorities[pos] )
	        {
	        	  swap(t,pos);
	              pos= t; 
	        }
	        else break;
	    }
	}

	@Override
	public String toString(int maxKeysToPrint) {
		if (maxKeysToPrint <= 0)
			maxKeysToPrint = Integer.MAX_VALUE;
		FixedBinaryHeapPriorityQueue<E> pq = this.clone();
		StringBuilder sb = new StringBuilder("[");
		int numKeysPrinted = 0;
		while (numKeysPrinted < maxKeysToPrint && pq.hasNext()) {
			double priority = pq.getPriority();
			E element = pq.next();
			sb.append(element.toString());
			sb.append(":");
			sb.append(priority);
			if (numKeysPrinted < size() - 1)
				sb.append(", ");
			numKeysPrinted++;
		}
		if (numKeysPrinted < size())
			sb.append("...");
		sb.append("]");
		return sb.toString();
	}
	
	@Override
	public FixedBinaryHeapPriorityQueue<E> clone() {
		FixedBinaryHeapPriorityQueue<E> clonePQ = new FixedBinaryHeapPriorityQueue<E>(capacity);
		clonePQ.size = size;
		clonePQ.capacity = capacity;
		clonePQ.elements = new ArrayList<E>(capacity);
		clonePQ.priorities = new double[capacity+1];
		if (size() > 0) {
			clonePQ.elements.addAll(elements);
			System.arraycopy(priorities, 0, clonePQ.priorities, 0, size()+1);
		}
		return clonePQ;
	}
	
	
	public static void main(String[] args) {
		
		FixedBinaryHeapPriorityQueue<Integer> queue = new FixedBinaryHeapPriorityQueue<Integer>(10);
		//System.out.println(pq);
		for (int i = 0; i <10000; i++) {
			queue.add(i, i);
		}
		
	
		System.out.println(queue.findTopN().toString());
		System.out.println(queue.size());
//		while(queue.hasNext()){
//			System.out.println(queue.next());
//		}
		
		
		
	}
	
}